package com.atguigu.day02;

import java.util.ArrayList;
import java.util.HashMap;

// 有向无环图的实现
public class Example2 {
    public static void main(String[] args) {
        // key: 顶点
        // value: 顶点key指向的所有顶点所组成的列表
        HashMap<String, ArrayList<String>> dag = new HashMap<>();

        // "A" -> ["B","C"]
        ArrayList<String> ANeighbors = new ArrayList<>();
        ANeighbors.add("B");
        ANeighbors.add("C");
        dag.put("A", ANeighbors);

        // "B" -> ["D","E"]
        ArrayList<String> BNeighbors = new ArrayList<>();
        BNeighbors.add("D");
        BNeighbors.add("E");
        dag.put("B", BNeighbors);

        // "C" -> ["D","E"]
        ArrayList<String> CNeighbors = new ArrayList<>();
        CNeighbors.add("D");
        CNeighbors.add("E");
        dag.put("C", CNeighbors);

        // 找出从source到sink的所有路径
        // A --> B --> D
        // A --> B --> E
        // A --> C --> D
        // A --> C --> E

        // 拓扑排序
        // topologicalSort(有向无环图，起点，待打印路径的字符串)
        topologicalSort(dag, "A", "A");
    }

    public static void topologicalSort(
            HashMap<String, ArrayList<String>> dag,
            String vertex,
            String path
    ) {
        if (vertex.equals("D") || vertex.equals("E")) {
            // 如果当前遍历的顶点是终点D或者E，那么直接打印路径
            System.out.println(path);
        } else {
            // 如果遍历的顶点不是终点，那么将当前顶点添加到路径，
            // 然后继续遍历当前顶点指向的所有顶点
            for (String v : dag.get(vertex)) {
                topologicalSort(dag, v, path + " ==> " + v);
            }
        }
    }
}
// 递归调用的其中一个调用栈
// topologicalSort(dag, "A", "A");
// topologicalSort(dag, "B", "A ==> B");
// topologicalSort(dag, "D", "A ==> B ==> D");